In a compiler, register allocation is the problem of mapping program variables to machine registers for the purpose of fast execution. Researchers and compiler writers have used a variety of approaches to model register allocation, including graph coloring [9, 17], integer linear programming [2, 10], partitioned Boolean quadratic optimization [16, 11], and multi-commodity network flow [13]. These approaches represent different tradeoffs between compilation speed and quality of the produced code. For example, linear scan [15] is a simple algorithm based on the coloring of interval graphs that produces code of reasonable quality with fast compilation time; iterated register coalescing [9] is a more complicated algorithm that, although slower, tends to produce code of better quality than linear scan. Finally, the Appel-George algorithm [2] achieves optimal spilling with respect to a cost model in worst-case exponential time via integer linear programming.